package 代码随想录.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _11完全二叉树的节点个数 {
    /**
     * 222. 完全二叉树的节点个数
     * https://leetcode.cn/problems/count-complete-tree-nodes/
     * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
     * 完全二叉树 的定义如下：
     * 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
     * 并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。
     */
    public int countNodes(TreeNode root) {
        if(root==null)
            return 0;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
    public int countNodes2(TreeNode root) {
        int cnt = 0;
        if(root==null)
            return cnt;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            TreeNode node = q.poll();
            cnt++;
            if(node.left!=null)
                q.offer(node.left);
            if(node.right!=null)
                q.offer(node.right);
        }
        return cnt;
    }

    //利用完全二叉树的性质
    // 满二叉树的结点数为：2^depth - 1
    public int countNodes3(TreeNode root) {
        if (root == null) return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        while (left != null) {  // 求左子树深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) { // 求右子树深度
            right = right.right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            //满二叉树
            return (2 << leftDepth) - 1;
        }
        return  countNodes(root.left) + countNodes(root.right) + 1;
    }

}
